This disclosure relates generally to the field of computerized problem solving and in particular to a system and method for tuning solving behavior by utilizing resource bounds.
In certain control system applications, there exists a significant need for systems which can provide satisfactory decisions in critically time-constrained situations for complex systems having subsystems consisting of many networked sensors and actuators, with each subsystem having control, monitoring and fault diagnosis capabilities. Advances in hardware technology, such as inexpensive processors, low-cost micro-electromechanical systems (MEMS) actuators and sensors, and decreasing communication costs, result in systems with unprecedented reconfigurability, flexibility, and robustness. Such applications would benefit from the use of generic problem solvers, such as constraint solvers, to improve fault tolerance and reconfigurability. However, such problem solvers are typically not able to adapt their execution to or even execute within the resource bounds of the applications, such as time and memory limits.
One problem solving technique for such systems is off-line adaptive problem solving, or what might be called open-loop control of solving, in which some parameters are learned off-line and the solver is then run with different parameter values depending on the problem instance. Various approaches have utilized feedback-type information, such as that suggested by Borrett, Tsang and Walsh. in “Adaptive Constraint Satisfaction: the Quickest First Principle”, Technical Report CSM-256, University of Essex Department of Computer Science, 1995, which uses on-line performance feedback to switch between solving algorithms, or Horvitz, Ryan, Gomes, Kautz, Selman and Chickering, “A Bayesian Approach to Tackling Hard Computational Problems”, Proceedings of the Seventheenth Conference on Uncertainty and Artifical Intelligence, Seattle, Wash., August 2001, which use it as part of a dynamic restart policy.
There are also a variety of approaches that dynamically build up estimates of value or cost functions to guide the search, such as Baluja et al., “Statistical Machine Learning for Large-scale Optimization”, Neural Computing Surveys, 3:1–58, 2000. In this case, functions are measurements of the “goodness” of particular states or action choices, and are developed on-line using accumulated performance data. In the evolutionary algorithms community, a variety of techniques have been used to adapt genetic operators and parameters based on various performance measures, as in Eiben, Hinterding, and Michalewicz, “Parameter Control in Evolutionary Algorithms”, IEEE transactions on evolutionary computation, 3:124–141, 1999. Similar approaches have been used with other techniques, such as simulated annealing, as in Wah & Wang, “Tuning Strategies in Constrained Simulated Annealing for Nonlinear Global Optimization”, International Journal of Artificial Intelligence Tools, 9(1), 2000.
Such techniques have also been used to modify the problem representation, as in the “open-loop” off-line design approach for problem reformulation proposed by Hnich and Flener in “High-level Reformulation of Constraint Programs”, Proceedings of the Tenth International French Speaking Conference on Logic and Constraint Programming, pages 75–89, 2001. Feedback approaches have been used as well. For example, Pemberton and Zhang, “ε-transformation: Exploiting Phase Transitions to Solve Combinatorial Optimization problems”, Artificial Intelligence 81(1–2):297–325, 1996, uses (open-loop) phase transition information and on-line branching estimation to identify complex search problems and transform them into easier searches producing sub-optimal solutions. Modification of penalty weights or chromosome representations in response to performance has also been explored in the evolutionary algorithms community by Eiben et al., “Parameter Control in Evolutionary Algorithms”.
However, these techniques do not utilize a generic framework, nor are they time-bounded, explicitly taking a time bound, a time value by when a solution must be computed, into account when selecting solver parameter values. Although some of these techniques represent anytime algorithms that can be stopped when a time bound is reached, the time bound is not considered earlier. Additionally, none of these techniques consider resource limits such as limits in computing memory.